package codetop.kuaishou.T662;

import util.TreeNode;

import java.util.Arrays;

/**
 * @Author: 18362
 * @Create: 2022-09-15 23:46:49 星期四
 */
class Solution {
    private int[] mins = new int[3000];
    private int[] maxs = new int[3000];
    private int height = 0;

    public int widthOfBinaryTree(TreeNode root) {
        Arrays.fill(mins, -1);
        dfs(root, 0, 0);
        int width = 0;
        for (int i=0; i<=height; ++i) {
            if (mins[i] >= 0)
                width = Math.max(width, maxs[i]-mins[i]+1);
        }
        return width;
    }

    private void dfs(TreeNode root, int level, int num) {
        if (root == null)
            return;
        height = Math.max(height, level);
        if (mins[level] == -1) {
            mins[level] = num;
            maxs[level] = num;
        } else {
            mins[level] = Math.min(mins[level], num);
            maxs[level] = Math.max(maxs[level], num);
        }
        dfs(root.left, level+1, 2*num+1);
        dfs(root.right, level+1, 2*num+2);
    }
}
